{ "cells": [ { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "all_ = []\n", "for i in range(100):\n", " all_.append(id(i))" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(all_) == len(set(all_))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 2, 2]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "l = [1,2] + [2]\n", "l" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", " ____11_______\n", " / \\\n", " __12 ___6\n", " / \\ / \\\n", "1 13 14 0\n", " \\ / \\ \\\n", " 4 2 3 7\n", "\n" ] } ], "source": [ "from binarytree import tree\n", "\n", "my_tree = tree(height=3, is_perfect=False)\n", "print(my_tree)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 4, 12, 13, 11, 2, 14, 3, 6, 0, 7]\n", "0\n" ] } ], "source": [ "class Solution:\n", " def diameterOfBinaryTree(self, root) -> int:\n", " print(self.travel(root, []))\n", " return 0\n", " \n", " def travel(self, node, l):\n", " if node is None:\n", " return []\n", " return self.travel(node.left, l) + [node.val] + self.travel(node.right, l)\n", "print(Solution().diameterOfBinaryTree(my_tree))" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 4, 12, 13, 11, 2, 14, 3, 6, 0, 7]\n", "0\n" ] } ], "source": [ "class Solution:\n", " def diameterOfBinaryTree(self, root) -> int:\n", " self.l, self.r = [], []\n", " print(list(self.traverse(root)))\n", " return 0\n", " \n", " def traverse(self, tree):\n", " if tree.left is not None:\n", " yield from self.traverse(tree.left)\n", "\n", " yield tree.value\n", "\n", " if tree.right is not None:\n", " yield from self.traverse(tree.right)\n", "print(Solution().diameterOfBinaryTree(my_tree))" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", " ____________7______________\n", " / \\\n", " ____9___ _________28__\n", " / \\ / \\\n", " _16 _13 _1___ 25\n", " / \\ / \\ / \\ /\n", "10 15 14 20 27 _24 4\n", " \\ / \\\n", " 19 12 17\n", "\n" ] }, { "data": { "text/plain": [ "8" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " maxLevel = None\n", " \n", " def diameterOfBinaryTree(self, root) -> int:\n", " self.maxLevel = 0\n", " self.travel(root)\n", " return self.maxLevel\n", " \n", " def travel(self, node):\n", " current = node\n", " if current == None:\n", " return\n", " \n", " level = self.findLevels(node.left) + self.findLevels(node.right)\n", " if level > self.maxLevel:\n", " self.maxLevel = level\n", " \n", " self.travel(node.left)\n", " self.travel(node.right)\n", " \n", " def findLevels(self, root):\n", " if root == None:\n", " return 0\n", " \n", " #list_of_vals = []\n", " level_list = [[root]]\n", " \n", " while True:\n", " current_level = level_list[-1]\n", " #print(current_level)\n", " level_list.append([])\n", " i = 0\n", " while i < len(current_level):\n", " node = current_level[i]\n", "\n", " #list_of_vals.append(node.val)\n", "\n", " if node.left:\n", " level_list[-1].append(node.left)\n", "\n", " if node.right:\n", " level_list[-1].append(node.right)\n", " \n", " i += 1\n", " \n", " if len(level_list[-1]) == 0:\n", " break\n", "\n", " #list_of_vals.append(f\"__{len(level_list)}__\")\n", " \n", " return len(level_list)-1\n", " \n", "\n", "my_tree = tree(height=4, is_perfect=False)\n", "print(my_tree)\n", "Solution().diameterOfBinaryTree(my_tree)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "https://leetcode.com/problems/diameter-of-binary-tree\n", "\n", "\n", "\n", "Runtime: 824 ms, faster than 5.01% of Python3 online submissions for Diameter of Binary Tree.\n", "Memory Usage: 16 MB, less than 77.08% of Python3 online submissions for Diameter of Binary Tree.\n", "\n", "\n", "\n", "```py\n", "class Solution:\n", " maxLevel = None\n", " \n", " def diameterOfBinaryTree(self, root) -> int:\n", " self.maxLevel = 0\n", " self.travel(root)\n", " return self.maxLevel\n", " \n", " def travel(self, node):\n", " current = node\n", " if current == None:\n", " return\n", " \n", " level = self.findLevels(node.left) + self.findLevels(node.right)\n", " if level > self.maxLevel:\n", " self.maxLevel = level\n", " \n", " self.travel(node.left)\n", " self.travel(node.right)\n", " \n", " def findLevels(self, root):\n", " if root == None:\n", " return 0\n", " \n", " #list_of_vals = []\n", " level_list = [[root]]\n", " \n", " while True:\n", " current_level = level_list[-1]\n", " #print(current_level)\n", " level_list.append([])\n", " i = 0\n", " while i < len(current_level):\n", " node = current_level[i]\n", "\n", " #list_of_vals.append(node.val)\n", "\n", " if node.left:\n", " level_list[-1].append(node.left)\n", "\n", " if node.right:\n", " level_list[-1].append(node.right)\n", " \n", " i += 1\n", " \n", " if len(level_list[-1]) == 0:\n", " break\n", "\n", " #list_of_vals.append(f\"__{len(level_list)}__\")\n", " \n", " return len(level_list)-1\n", "```\n", "\n", "\n", "Spent 8 hours\n", "\n", "Get failed for 11 times" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }